package com.gitee.feizns.explore.data_structure.heap;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author feizns
 * @since 2019/11/19
 */
public class MaxHeap<E extends Comparable<E>> {

    public static void main(String[] args) {
        MaxHeap<Integer> heap = new MaxHeap<>();
        Random random = new Random();
        for (int i = 0; i < 100000; i++) { heap.siftUp((Integer) random.nextInt(1000000)); }

        System.out.println(heap.extractMax());

        System.out.println(heap.replace(12));

        System.out.println(heap.extractMax());

        System.out.println("END");
    }

    private List<E> arr = new ArrayList<>();

    public int size() { return arr.size(); }

    public boolean isEmpty() { return arr.isEmpty(); }


    public int parent(int index) {
        if ( index == 1 ) return 0;
        if ( index > 1 )
            return (index - 1) / 2;
        throw new RuntimeException("INDEX ...");
    }

    private int left(int index) {
        return index * 2 + 1;
    }

    private int right(int index) {
        return index * 2 + 2;
    }

    public void siftUp(E e) {
        arr.add(e);
        siftUp(arr.size() - 1);
    }

    private void siftUp(int index) {
        if ( index > 0 ) {
            int parent = parent(index);
            if ( arr.get(parent).compareTo(arr.get(index)) < 0 ) {
                swap(parent, index);
                siftUp(parent);
            }
        }
    }

    public E extractMax() {
        if ( !arr.isEmpty() ) {
            E e = arr.get(0);
            E last = arr.get(size() - 1);
            arr.set(0, last);
            arr.remove(size() - 1);
            siftDown(0);
            return e;
        }
        return null;
    }

    public E replace(E e) {
        if ( !arr.isEmpty() ) {
            E ret = arr.get(0);
            arr.set(0, e);
            siftDown(0);
            return ret;
        }
        return null;
    }

    private void siftDown(int index) {
        int l = left(index);
        int r = right(index);

        int child = (r < size() && l < size())
                ? (arr.get(l).compareTo(arr.get(r)) > 0 ? l : r)
                : ((r < size()) ? r : (l < size()) ? l : -1);

        if ( child != -1 && arr.get(index).compareTo(arr.get(child)) < 0 ) {
            swap(index, child);
            siftDown(child);
        }
    }

    private void swap(int i, int j) {
        E tmp = arr.get(i);
        arr.set(i, arr.get(j));
        arr.set(j, tmp);
    }

}
